package leetcode_2501_2600;

public class LeeCode_2585 {
    public static void main(String[] args) {
        System.out.println(waysToReachTarget(6, new int[][]{{6, 1}, {3, 2}, {2, 3}}));
    }
    private static int waysToReachTarget(int target, int[][] types) {
        long mod = (long) (1e9 + 7);
        int n = types.length;
        long[][] dp = new long[n][target + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= types[0][0]; i++) {
            int sco = types[0][1] * i;
            if (sco > target)
                break;
            dp[0][sco] = 1;
        }
        for (int i = 1; i < n; i++) {
            int[] type = types[i];
            int count = type[0], score = type[1];
            for (int j = 0; j <= count; j++) {
                int add = j * score;
                for (int k = 0; k <= target - add; k++) {
                    dp[i][k + add] += dp[i - 1][k];
                    dp[i][k + add] %= mod;
                }
            }
        }
        return (int) dp[n - 1][target];
    }
}